"""
https://leetcode.cn/problems/generate-parentheses/description/

22. 括号生成
已解答
中等
相关标签
相关企业
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

提示：

1 <= n <= 8

"""
from typing import List


class Solution:
    """
    先从数学上考虑，n是如何决定有效括号的种类的
    有效括号的判定方法是，在括号对应的数字记录下，从0开始，遇到左括号则+1，遇到右括号则-1。最后得到的数组，每个数字都不小于0。
    同样的可以发现，只要确定了左括号的索引位置，则右括号的索引位置也就被确定了。

    考虑回溯法，假定已经获得了左半区的所有可能，要继续计算右侧的下一个可能性。
    维护的状态：使用的左括号的数量ln、右括号的数量rn
    - 如果rn==n，则结束并返回所有结果
    - 如果ln==n，则只能使用右括号（rn+1）
    - 如果ln==rn，则只能使用左括号（ln+1）
    - 如果ln>rn（其他所有情况），则既可以使用左括号，也可以使用右括号
    
    假定从n开始向n-1回溯
    
    
    """
    def generateParenthesis(self, n: int) -> List[str]:
        
        def backtrack(ln=0,rn=0,res=['']):
            if rn==n:
                return res
            if ln==n:
                res=[f'{_})' for _ in res]
                return backtrack(ln,rn+1,res)
            if ln==rn:
                res=[f'{_}(' for _ in res]
                return backtrack(ln+1,rn,res)
            else:
                res1=[f'{_})' for _ in res]
                res2=[f'{_}(' for _ in res]
                return backtrack(ln,rn+1,res1)+backtrack(ln+1,rn,res2)

            pass

        res=backtrack()

        return res

if __name__=='__main__':
    n=3
    s=Solution()
    res=s.generateParenthesis(n)
    print(res)
    pass